package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Arrays;
import java.util.Scanner;

/*
有n个重量和价值分别为wi，vi的物品，从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。
    1 ≤ n ≤ 100
    1 ≤ wi ≤ 100
    1 ≤ vi ≤ 100 
    1 ≤ W ≤ 10000

输入：
    n=4
    (w,v)={(2,3),(1,2),(3,4),(2,2)}
    W=5

输出：
    7（选择第0，1，3号物品）

因为对每个物品只有选和不选两种情况，所以这个问题称为01背包。


5
1 2 3 4 5
1 4 3 4 1
10

12
 */
public class e背包问题byDFS记忆性递归plus01背包 {
	public static void main(String[] args) {
		e背包问题byDFS记忆性递归plus01背包 test = new e背包问题byDFS记忆性递归plus01背包();
		long time = System.currentTimeMillis();
		test.useDFSKnapsackMemory1();
//		test.useDFSKnapsackMemory();
		util.Util.duration(time);
	}
	
	public void useDFSKnapsackMemory1() {
		int[] weight = new int[] {1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5};
		int[] value = new int[] {1, 4, 3, 4, 1, 1, 4, 3, 4, 1, 1, 4, 3, 4, 1};
		int[][] recall = new int[15][31];
		for (int i = 0; i < 15; i++) {
			Arrays.fill(recall[i], -1);//初始化备忘录；是矩阵每一个元素都是-1
		}
		
		int res = DFSKnapsackMemory(weight, value, 30, 15, 0, recall);
		
		System.out.println(res);
	}
	
	/**
	 * 前置方法
	 * 动态规划可以说是
	 * 记忆性递归
	 * 也称带备忘录的递归
	 */
	public void useDFSKnapsackMemory() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int[] weight = new int[N];
		int[] value = new int[N];
		for (int i = 0; i < N; i++) {
			weight[i] = scanner.nextInt();
		}
		for (int i = 0; i < N; i++) {
			value[i] = scanner.nextInt();
		}
		int maxWeight = scanner.nextInt();
		int[][] recall = new int[N][maxWeight + 1];//备忘录
		for (int i = 0; i < N; i++) {
			Arrays.fill(recall[i], -1);//初始化备忘录；是矩阵每一个元素都是-1
		}
		int res = DFSKnapsackMemory(weight, value, maxWeight, N, 0, recall);//记忆性递归
		System.out.println(res);
	}
	
	/**
	 * 记忆性递归
不需要回溯的原因是
	我们在一次A使用DFSKnapsack中
	虽然有两次B,C又使用了DFSKnapsack
	但我们在A次的maxWeight，current都没有被改变
	我们传进B,C的动态参数是
		maxWeight - weight[current]
		current + 1
	并没有对A的maxWeight，current造成改变
	所以不需要回溯
	 * @param weight
	 * @param value
	 * @param maxWeight
	 * @param N
	 * @param current
	 * @param recall
	 * @return
	 */
	public int DFSKnapsackMemory(int[] weight, int[] value, int maxWeight, int N, int current, int[][] recall) {
		if (maxWeight <= 0) {
			return 0;
		}
		if (current == N) {
			return 0;
		}
		if (recall[current][maxWeight] >= 0) {//查询备忘录
			return recall[current][maxWeight];
		}
		int temp = 0;
		int valueNoSelect = DFSKnapsackMemory(weight, value, maxWeight, N, current + 1, recall);
		if (weight[current] <= maxWeight) {
			int valueSelect = value[current] + DFSKnapsackMemory(weight, value, maxWeight - weight[current], N, current + 1, recall);
			temp = Math.max(valueNoSelect, valueSelect);
		} else {
			temp = valueNoSelect;
		}
		//不管选没选，current下的maxWeight此时的节点的值，是唯一的。就是temp。所以直接存[current][maxWeight]这个位置没毛病
		recall[current][maxWeight] = temp;//存入备忘录
		return temp;
	}
		
}
